Medium
Related Topics: Array / Dynamic Programming / Greedy
LeetCode Source

解題想法

先初始化一些變數

• max_reach = 0 # current max index that can be reached
• max_len = len(nums) # the length of nums
• res = 0 # the minimum number of jumps

主要思路是判斷當前可觸及的長度有無超越 nums 的長度

如果有則回傳 res

否則更新當前 cur_max_reach

而在由 index 0 到 cur_max_reach 的值更新 max_reach

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_reach = 0  # current max index that can be reached
        max_len = len(nums)  # the length of nums
        res = 0  # the minimum number of jumps

        if max_len == 1:
            return 0

        while max_reach < max_len - 1:
            res += 1
            cur_max_reach = max_reach
            for i in range(cur_max_reach + 1):
                max_reach = max(max_reach, i + nums[i])

        return res

C++

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, max_len = nums.size(), max_reach = 0;
        if (max_len == 1)
            return 0;
        while (max_reach < max_len - 1) {
            res += 1;
            int cur_max_reach = max_reach;
            for (int i = 0; i < cur_max_reach + 1; i++)
                max_reach = max(max_reach, i + nums[i]);
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series